package org.example.SolutionNew005;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

public class Backtrack001 {
    public static void main(String[] args) {
        Backtrack001 obj=new Backtrack001();
        int[] nums=new int[]{1,2,3};
        System.out.println(obj.permute(nums).toString());
    }

    //第一次尝试，就是空间太大了
    List<List<Integer>> res;
    public List<List<Integer>> permute1(int[] nums) {
        res=new ArrayList<>();
        List<Integer> l=new ArrayList<>();
        List<Integer> list=Arrays.stream(nums).boxed().collect(Collectors.toList());
        searchAllList(list,l);
        return res;
    }

    public void searchAllList(List<Integer> list,List<Integer> l){
        int n=list.size();
        for(int i=0;i<n;i++){
            l.add(list.get(i));
            List<Integer> newList=new ArrayList<>(list);
            newList.remove(i);
            if(n-1==0){
                res.add(new ArrayList<>(l));
            }else{
                searchAllList(newList,l);
            }
            l.remove(l.size()-1);
        }
    }

    //第二次在一个list的基础上进行交换得到答案
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        List<Integer> list=Arrays.stream(nums).boxed().collect(Collectors.toList());
        int n=list.size();
        getList(res,list,n,0);
        return res;
    }

    public void getList(List<List<Integer>> res,List<Integer> list,int n,int start){
        if(start==n){
            res.add(new ArrayList<>(list));
        }else{
            for(int i=start;i<n;i++){
                Collections.swap(list,i,start);
                getList(res,list,n,start+1);
                Collections.swap(list,i,start);
            }
        }
    }
}
